#include "CommonHead.h"
#include "DesignPattern.h"
#include <queue>

class Solution
{
private:
	static constexpr int numOfAlpha = 26;
public:
	string reorganizeString(string S)
	{
		if (S.size() < 2)
		{
			return S;
		}
		vector<int> Counter(numOfAlpha, 0);
		int MaxCount = 0, Length = S.size();

		// 统计字母出现的频率（以及出现的最大频率）
		for (size_t i = 0; i < Length; i++)
		{
			char c = S[i];
			Counter[c - 'a']++;
			MaxCount = Counter[c - 'a'] > MaxCount ? Counter[c - 'a'] : MaxCount;
		}

        // 出现频率最高的字母不超过总数的一半，无有效解
		if (MaxCount > (Length + 1) / 2)
		{
			return "";
		}

		auto cmp = [&](const char& elem1, const char& elem2)->bool
		{
			return Counter[elem1 - 'a'] < Counter[elem2 - 'a'];
		};

		// 构建优先队列
		priority_queue<char, vector<char>, decltype(cmp)> MyPriorQueue(cmp);

		// 有效元素入队
		for (size_t i = 0; i < numOfAlpha; i++)
		{
			if (Counter[i] > 0)
			{
				MyPriorQueue.push(i + 'a');
			}
		}

		// 两两为一组执行出队（贪心算法）
		string ret;
		while (MyPriorQueue.size() > 1)
		{
			char elem1 = MyPriorQueue.top();  MyPriorQueue.pop();
			char elem2 = MyPriorQueue.top();  MyPriorQueue.pop();

			ret += elem1;
			ret += elem2;

			int index1 = elem1 - 'a', index2 = elem2 - 'a';
			if (--Counter[index1] > 0)
			{
				MyPriorQueue.push(elem1);
			}
			if (--Counter[index2] > 0)
			{
				MyPriorQueue.push(elem2);
			}
		}

		if (MyPriorQueue.size() > 0)
		{
			ret += MyPriorQueue.top();
		}
		return ret;
	}
};

